Wie ordnet man viele gleich große Kugeln möglichst dicht dreidimensional an? Obsthändler lösen das Problem täglich, wenn sie ihre Orangen zu eindrucksvollen Pyramiden aufschichten. Logischerweise wird man versuchen, jede neue Kugel so dicht wie möglich an den bereits vorhandenen Haufen anzulagern. Man legt also die zweite direkt neben die erste und fügt die dritte so an, daß sie die beiden anderen berührt; die Kugelmittelpunkte bilden dann ein gleichseitiges Dreieck. Nach diesem Muster läßt sich mühelos die gesamte Tischfläche bedecken – kein Wunder, denn man kann die Ebene lückenlos mit gleichseitigen Dreiecken pflastern.

Auf diese erste Lage schichtet man eine zweite, gleichartige; deren Kugeln legen sich wie von selbst in die Lücken, die je drei Kugeln der unteren Schicht lassen (Bild). Nur wer genau aufpaßt, merkt, daß jede zweite dieser Lücken frei bleibt; es gibt gewissermaßen schwarze (gefüllte) und weiße (freie) Lücken, die sich in dem Dreiecksmuster schachbrettartig abwechseln. In die Lücken der zweiten Schicht – entweder in die weißen oder in die schwarzen – legt man die dritte, und so weiter. Da man sich bei jeder Schicht aufs neue für schwarz oder weiß entscheiden kann, gibt es unendlich viele gleichberechtigte Anordnungen dieser Art.

Eine Packung von Kugeln kann natürlich den Raum niemals so vollständig ausfüllen wie ein Stapel von Würfeln – zwischen den krummen Kugeloberflächen bleiben zwangsläufig immer gewisse Zwickel frei. Bei der beschriebenen Anordnung beträgt der von den Kugeln ausgefüllte Anteil des Gesamtvolumens p/SQRT18; das sind immerhin 74,048 Prozent.

Daß es nicht besser geht, hat der Mathematiker und Astronom Johannes Kepler, besser bekannt für seine Gesetze der Planetenbewegung, schon 1611 vermutet. Nur konnte er es nicht beweisen – und Generationen von Mathematikern nach ihm ebensowenig. Damit hat dieses Problem den Lösungsversuchen der Fachleute sogar etwas länger widerstanden als die ungleich berühmtere Fermatsche Vermutung. Erst im vergangenen Sommer hat Thomas Hales von der Universität von Michigan in Ann Arbor einen Beweis präsentiert – allerdings sehr vorsichtig, unter dem Vorbehalt der Nachprüfung durch die Fachkollegen. Gerade zur Fermatschen Vermutung hatte es dabei ja noch böse Überraschungen gegeben (Spektrum der Wissenschaft, Januar 1998, Seite 96). Außerdem mußten schon etliche Beweisversuche zur Kepler-Vermutung kleinlaut zurückgezogen werden; nur Wu-Yi Hsiang von der Universität von Kalifornien in Berkeley hält seine Argumentationskette im Gegensatz zum Rest der mathematischen Welt immer noch für stichhaltig.

Im Gegensatz zu Andrew Wiles, der seinen Beweis der Fermatschen Vermutung im stillen Kämmerlein ausgeheckt und zunächst nur ausgewählten Fachkollegen vorgelegt hatte, machte Hales aus seiner Arbeit, auch in Zwischenstadien, nie ein Geheimnis. Sein Werk liegt für alle Welt zur Begutachtung im Internet offen (http://www.math.lsa.umich.edu/~hales/kepler.html).



Gründe für das bisherige Scheitern




Warum ist es so schwer, eine anscheinend offensichtliche Tatsache nach den strengen Regeln der Kunst zu beweisen? Erstens vermag man sich andere, möglicherweise bessere Lösungen als die naheliegendste kaum vorzustellen. Eine Denkhemmung wird dabei durch den Tisch verursacht: Man neigt unwillkürlich dazu, die Kugeln in Gedanken zunächst auf eine Ebene zu legen. Das ist jedoch keineswegs zwingend. Beschränkt man sich allerdings auf Packungen, in denen die Kugeln so regelmäßig angeordnet sind wie Atome in einem Kristallgitter, dann stellt sich als kompakteste Version die kubisch-flächenzentrierte heraus (bei der die Kugeln in den Ecken und den Flächenmitten von dicht an dicht gestapelten Würfeln sitzen), und die entsteht durch das beschriebene Stapeln ebener Dreiecksgitter, wenn man nach einer bestimmten Systematik die weißen oder schwarzen Lücken füllt. Kandidaten für noch bessere Packungen müssen also unordentlicher sein.

Zweitens geht es, genau besehen, stets um eine unendliche Zahl von Kugeln. Die Aufgabe, möglichst viele Orangen in eine Kiste zu packen, ist etwas völlig anderes, und ihre Lösung hängt vor allem für kleine Kisten entscheidend von deren Form ab (siehe "Mathematische Unterhaltungen", März 1999, Seite 112). Beim Kepler-Problem gibt es dagegen unendlich viele variierbare Größen: die Kugelmittelpunkte. Wie soll man beweisen, daß in dieser wahrlich gigantischen Auswahl keine Anordnung existiert, die vielleicht doch eine größere Packungsdichte hat als die bekannte?

Drittens, und das ist die entscheidende Schwierigkeit, gibt es auf sehr kleinem Raum sehr wohl dichtere Kugelpackungen als die Keplersche. Ordnet man drei Kugeln im Dreieck an und setzt eine vierte in die Mitte obenauf, bilden ihre Mittelpunkte ein reguläres Tetraeder (einen der fünf platonischen Körper), und die Kugeln füllen das Tetraeder zu 77,9636 Prozent (Bild auf Seite 11). Mit einer Packung, die ausschließlich oder zumindest zum größten Teil aus solchen Tetraeder-Anordnungen besteht, wäre also die Kepler-Dichte zu übertreffen. Es gilt also zu beweisen, daß es solche Packungen nicht geben kann, weil eine Tetraeder-Anordnung um sich Kugeln in ungünstigerer Position erzwingt.

Zu diesem Zwecke zeigte Hales zunächst, daß der lokale Dichtevorteil der Tetraeder-Anordnung nicht erst weit draußen, sondern bereits in der näheren Umgebung wieder aufgezehrt wird: Statt unendlich vieler Kugeln genügt es, Klumpen von höchstens 53 Kugeln zu betrachten.



Reduktion auf endlich viele Unbekannte




Damit hatte Hales das Problem auf endlich viele Unbekannte reduziert. Es blieben nur noch 5000 Typen von Klumpen zu untersuchen, und dabei ließ sich der Computer als Helfer einsetzen. Seine Funktion beschränkte sich allerdings auf die Buchhaltung und eine große Zahl von Hilfsrechnungen – im Gegensatz zum berüchtigten Computerbeweis des Vierfarbensatzes, den niemand ohne elektronische Unterstützung nachvollziehen kann.

In der Keplerschen Packung grenzen die regulären Tetraeder stets an reguläre Oktaeder. Bei diesem platonischen Körper aus acht gleichseitigen Dreiecken liegen vier Kugeln im Quadrat und eine weitere sitzt jeweils über und unter dem Loch in der Mitte. Die Dichte dieser Anordnung beträgt nur 72,0903 Prozent (Bild auf Seite 11).

Immerhin kann man den Raum lückenlos mit einer Kombination aus Tetraedern und Oktaedern füllen, wobei nie zwei Körper der gleichen Sorte mit einer Fläche aneinandergrenzen; die Keplersche Packung entspricht genau dieser Pflasterung des Raumes.

Hales bilanzierte das von den Kugeln ausgefüllte Teilvolumen mit einer Art doppelten Buchführung. Dabei nahm er die Packungsdichte im Inneren eines Oktaeders als Bewertungsmaßstab. Den Zugewinn an Dichte, den ein Tetraeder bietet, nennt Hales einen Punkt. Sein Beweis läuft darauf hinaus, durch Untersuchung der 5000 Einzelfälle zu zeigen, daß keine Anordnung von Kugeln in der näheren Umgebung einer bestimmten Kugel mehr als acht Punkte erreichen kann. Es geht also nie besser als mit den acht Tetraedern, die in der Kepler-Packung einem Oktaeder anliegen.



Trickreiche doppelte Buchführung




Für die erste Art der Bilanzierung muß man die Mittelpunkte benachbarter Kugeln durch Kanten verbinden und die Polyeder studieren, die aus diesen Kanten entstehen. Dabei ist man genötigt, auch Kugeln als benachbart anzusehen, die einander zwar nahe sind, sich aber nicht berühren; anderenfalls hätte man sich mit sehr merkwürdig geformten Polyedern herumzuschlagen. Damit ist die Zerlegung des Raumes in Vielflächner aber nicht mehr eindeutig: Nichts hindert einen daran, ein Oktaeder durch ein Paar kreuzweise geführter Schnitte in vier (nicht-reguläre) Tetraeder zu zerlegen, ohne eine einzige neue Ecke einzuführen.

Dadurch gerät diese Art der Buchführung in bestimmten Fällen an ihre Grenzen. Deshalb zog Hales als Ergänzung eine zweite Bilanzierungsmethode heran, die stets dann zum Einsatz kam, wenn die erste versagte. Dabei legt man die Polyeder nicht mehr durch die Kugeln hindurch, sondern um sie herum. Jede Kugel bekommt gleichsam einen Vorgarten zugewiesen (der offizielle Name ist "Voronoi-Zelle"): die Menge aller Punkte, die ihrem Mittelpunkt näher liegen als dem jeder anderen Kugel. Dieser Vorgarten ist in der Kepler-Packung ein Rhombendodekaeder (Bild) – ein Polyeder, mit dem sich der Raum lückenlos füllen läßt (Spektrum der Wissenschaft, Juni 1994, Seite 12).

Je kleiner der Vorgarten, desto besser für die Packungsdichte. Was ist das kleinstmögliche Exemplar? Wie man seit dem vorigen Jahrhundert weiß, kann eine Kugel höchstens zwölf sie berührende Nachbarn haben (Spektrum der Wissenschaft, September 1992, Seite 12). Wie üblich, erreicht man das Minimum des Vorgartenvolumens durch die symmetrischste aller Anordnungen: die zwölf angrenzenden Kugeln in den Ecken eines regulären Ikosaeders. Das ergibt ein (platonisches) Dodekaeder (Bild) und eine Packungsdichte von 75,4737 Prozent; aber leider kann man auch diese regelmäßigen Zwölfflächner nicht lückenlos im Raum stapeln.

Durch geschickte Kombination beider Buchführungsverfahren gelang es Hales, sämtliche Einzelfälle zu erledigen. Dabei erwies sich eine einzige Anordnung als bei weitem härteste Nuß; Hales' Schüler Samuel Ferguson hat seine Dissertation darüber geschrieben. Die Kugeln sitzen in diesem Falle an den Ecken eines Prismas mit fünfeckiger Grundfläche und quadratischen Wänden, auf das oben und unten flache Hüte aus je fünf gleichseitigen Dreiecken aufgesetzt sind.

Am Ende führen all diese Überlegungen (und weitere hier nicht näher erläuterte) auf Minimierungsprobleme. Umgibt man zum Beispiel eine Kugel mit zwölf anderen, liegen diese keineswegs dichtgefügt aneinander, sondern haben noch eine Menge "Luft", um sich zu bewegen; je nach ihrer Position ändert sich aber das Vorgartenvolumen. Es gibt stets ein Kontinuum möglicher Anordnungen, und das bekommt man nur in den Griff, indem man unter sämtlichen Anordnungen einer Klasse die günstigste findet und dann nachweist, daß selbst die nicht besser ist als die Keplersche. Somit ist – in zahlreichen Einzelfällen – eine nichtlineare Funktion mehrerer Variabler zu minimieren.

Auch diese Aufgabe gingen Hales und Ferguson nicht direkt an, sondern approximierten sie durch ein lineares Minimierungsproblem mit linearen Nebenbedingungen. Dieses lösten sie mit der Technik branch and bound, die eigentlich für kombinatorische Optimierungsprobleme entwickelt worden ist (vergleiche "Die optimierte Odyssee", Seite 76). Auf diese Weise konnten zwei weit entfernte Gebiete der Mathematik zumindest über die verwendeten Hilfsmittel voneinander profitieren.


Aus: Spektrum der Wissenschaft 4 / 1999, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH